package features.advance.leetcode.tree.easy;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.ArrayList;
import java.util.List;

/**
 *  剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
 *
 *  难度：简单
 *
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 *
 *                  6
 *             2          8
 *         0     4      7    9
 *            3   5
 * 示例 1:
 *
 * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 * 输出: 6
 * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
 * 示例 2:
 *
 * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
 * 输出: 2
 * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
 *
 *
 * 说明:
 *
 * 所有节点的值都是唯一的。
 * p、q 为不同节点且均存在于给定的二叉搜索树中。
 * 注意：本题与主站 235 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
 *
 * @author LIN
 * @date 2021-07-07
 */
public class Offer68_1 {

    public static void main(String[] args) {
        String str = "[6,2,8,0,4,7,9,null,null,3,5]";
        TreeNode root = TreeUtil.stringToTreeNode(str);
        TreeNode p = new TreeNode<>(2);
        TreeNode q = new TreeNode<>(4);

        Solution solution = new Solution() {
        };
        TreeNode treeNode = solution.lowestCommonAncestor(root, p, q);
        System.out.println(treeNode);

    }

    static class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || p == null || q == null){
                return null;
            }
            List<TreeNode> pList = getPath(root,p);
            List<TreeNode> qList = getPath(root,q);
            TreeNode res = null;
            for(int i=0;i<pList.size() && i<qList.size();i++){
                if(pList.get(i) == qList.get(i)){
                    res = pList.get(i);
                }else{
                    break;
                }
            }
            return res;


        }

        /**
         * 遍历树，将目标节点的所有上级节点，放入集合里
         * @param root
         * @param v
         * @return
         */
        public List<TreeNode<Integer>> getPath(TreeNode<Integer> root, TreeNode<Integer> v){
            List<TreeNode<Integer>> list = new ArrayList<>();
            TreeNode<Integer> node = root;
            while(node.val != v.val){
                list.add(node);
                if(node.val < v.val){
                    node = node.right;
                }else{
                    node = node.left;
                }
            }
            list.add(node);

            return list;
        }
    }
}
